struct SAM
{
	int root,lst,cnt;
	struct node
	{
		int ch[26],par,val;
	}a[MAXN<<1];
	int newnode(int x)
	{
		a[++cnt].val=x;
		return cnt;
	}
	void init()
	{
		cnt=0;
		root=lst=newnode(0);
	}
	void extend(int c)
	{
		int np=newnode(a[lst].val+1),p=lst;
		while(p&&!a[p].ch[c])a[p].ch[c]=np,p=a[p].par;
		if(!p)a[np].par=root;
		else if(a[a[p].ch[c]].val==a[p].val+1)a[np].par=a[p].ch[c];
		else 
		{
			int nq=newnode(a[p].val+1),q=a[p].ch[c];
			memcpy(a[nq].ch,a[q].ch,sizeof(a[q].ch));
			a[nq].par=a[q].par;
			a[q].par=a[np].par=nq;
			while(p&&a[p].ch[c]==q)a[p].ch[c]=nq,p=a[p].par;
		}
		lst=np;
	}
}
